package practice;

import java.util.Scanner;

/**
 * 算法练习第三天
 */
public class Day3 {
    /**
     * 一维前缀和
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int q = in.nextInt();
            int[] nums = new int[n];
            for(int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }
            long[] dp = new long[n + 1];
            for(int i = 1; i <= n; i++) {
                dp[i] = dp[i - 1] + nums[i - 1];
            }
            for(int i = 0; i < q; i++) {
                int a = in.nextInt();
                int b = in.nextInt();
                long ret = dp[b] - dp[a - 1];
                System.out.println(ret);
            }
        }
    }
    /**
     * 二维前缀和
     */

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            int q = in.nextInt();
            int[][] nums = new int[n][m];
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    nums[i][j] = in.nextInt();
                }
            }
            long[][] dp = new long[n+1][m+1];
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + nums[i-1][j-1];
                }
            }
            for(int i = 0; i < q; i++) {
                int x1 = in.nextInt();
                int y1 = in.nextInt();
                int x2 = in.nextInt();
                int y2 = in.nextInt();
                //ps:需要将x1-1，y1-1
                long ret = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
                System.out.println(ret);

            }
        }
    }
    /**
     * 寻找数组的中心下标
     * 输入：nums = [1, 7, 3, 6, 5, 6]
     * 输出：3
     * 解释：
     * 中心下标是 3 。
     * 左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
     * 右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
     */
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] dpFirst = new int[n];
        int[] dpLast = new int[n];
        for(int i = 1; i < n; i++) {
            dpFirst[i] = dpFirst[i - 1] + nums[i - 1];
        }
        for(int i = n-2; i >= 0; i--) {
            dpLast[i] = dpLast[i + 1] + nums[i + 1];
        }
        for(int i = 0; i < n; i++) {
            if(dpLast[i] == dpFirst[i]) {
                return i;
            }
        }
        return -1;
    }

}
